1. Field of the Invention
The present invention is directed to a method and apparatus for a table lookup index that provides access to a table, such as an addressing table, in a fast and efficient manner. More specifically the table lookup index is for the transmission of data packets in a network switch.
2. Description of the Prior Art
In the world of data transmission it is necessary to transmit data as quickly as possible, in order to have almost instantaneous access to information.
Table lookups are frequently used to index information to give quick access to much needed data. For example in network switching it is imperative that when data is received in a port the appropriate port for output be identified in order to transfer data. Therefore table lookups are utilized to store information regarding incoming data that directs the incoming data to an appropriate port for output.
In the field of table look-ups there are several methods used to access information. One method is a linear index.
FIG. 1B illustrates a 64K table 100 that is linearly indexed. Index 105 for a 64K table is required to be 16 bits long (216=64K) to linearly access entries in the table. Since the index linearly accesses entries in the table, there is a one to one correspondence between each index and each table entry (i.e. each index has a corresponding table entry).
FIG. 1C is an illustration of a linear index into a 64K table. Indexes I(1), I(2), I(3) . . . are each linearly indexed into the 64K table giving a one to one correspondence between each index and each table entry. If indexes I(1), I(2), I(3) . . . each are 16 bits long an entry can be found in 16 clock cycles using standard binary searching. However, when a new address must be learned by inserting an entry or deleting an entry, it will take a long time to delete or insert the address from or to the table because the index must be sorted after each insertion and each deletion. In the worst case scenario each of the sixteen bit address indexes will have to be moved and sorted which will be time consuming. This sorting greatly degrades the performance of the switch. When the new address is inserted into the table, addresses will have to be moved up and/or down in order to make room for the new address. Therefore as the table size increases, the performance of the switch degrades.
Other methods make use of pointers, hash functions or tree functions to remedy the problem. Most of these methods, when implemented, have a “bad” worst case performance—particularly for insert and delete operations. As noted above, as the size of the table increases, performance becomes degraded. Some of the main reasons for the poor results are that the table size directly affects performance and the methods require extra storage and data structures.